package leetcode.剑指offer.前40;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/30 19:02
 * @description :
 */
public class 剑指_39_数组中出现次数超过一半的数字 {
    @Test
    public void test() {
        Solution solution = new Solution();
        solution.majorityElement(new int[]{3,2,3});
    }

    class Solution {
        public int majorityElement(int[] nums) {
            for (int i = nums.length / 2 - 1; i >= 0; i--) {
                adjust(nums, i, nums.length);
            }
            for (int i = nums.length - 1; i >= (nums.length - 1) / 2; i--) {
                int tmp = nums[0];
                nums[0] = nums[i];
                nums[i] = tmp;
                adjust(nums, 0, i);
            }
            return nums[nums.length / 2];
        }
        private void adjust(int[] arr, int parentIndex, int len) {
            int temp = arr[parentIndex];
            int childIndex = parentIndex * 2 + 1;
            while (childIndex < len) {
                if (childIndex + 1 < len && arr[childIndex + 1] > arr[childIndex]) {
                    childIndex++;
                }
                if (temp >= arr[childIndex]) break;
                arr[parentIndex] = arr[childIndex];
                parentIndex = childIndex;
                childIndex = childIndex * 2 + 1;
            }
            arr[parentIndex] = temp;
        }
    }


}
